emscripten
Downloading...

Resize canvas Lock/hide mouse pointer    


/ >> augmented_containers >> augmented_deque_t
jhcarl0814.github.io
	Augmented Containers
		Sequence
			augmented_*****_t
			augmented_********_t
		Associative
			augmented_***​/​***​/​********​/​********_t
		*****
			augmented_*****_t
augmented_containers::augmented_deque_t
#include<augmented_containers/augmented_deque.hpp> (one single header file library)
template<
	typename element_t,
	typename allocator_t = std::allocator<element_t>,
	typename requested_stride_to_projector_and_accumulator_map_t = std::tuple<>
> struct augmented_deque_t;
augmented_deque_t is an augmented, strictly double-ended queue. It's part of the augmented containers library, providing a stronger version of sequence containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input sequence changes, refresh output values/ranges in logarithmic time complexity).
Complexity Table
possible implementations: adding a side deque augmented balanced tree augmented_deque_t
range update O(N), O(distance(range)) if range's begin/end is at accumulation end O(distance(range)+(lg(N)-lg(distance(range)))) O(distance(range)+(lg(N)-lg(distance(range))))
subrange query O(distance(range)), O(1) if range's begin/end is at accumulation begin O(lg(distance(range))) O(lg(distance(range)))
enqueue O(1) O(lg(N)) O(1)
dequeue O(1) O(lg(N)) O(1)
modify element at either end, then update O(N), O(1) if at the accumulation end O(lg(N)) O(1)
How to achieve O(1) enqueue && O(1) dequeue && O(lg(N)) accumulation depth?
augmented_deque_t is a node-based container. First the element nodes forms a doubly linked list, then tree nodes organize them into prefect binary trees. The enqueue and dequeue operations are analogous to operator++ and operator-- in binary positional numeral system.
test_graphcluster_base3base3cluster_base2_low_passbase2_low_passcluster_base2base2base3_00000000base3_00010001base3_00020002base3_00100010base3_00110011base3_00120012base3_00200020base3_00210021base3_00220022base3_01000100base3_01010101base3_01020102base3_01100110base3_01110111base3_01120112base3_01200120base3_01210121base3_01220122base3_02000200base3_02010201base3_02020202base3_02100210base3_02110211base3_02120212base3_02200220base3_02210221base3_02220222base3_10001000base3_10011001base3_10021002base3_10101010base3_10111011base3_10121012base3_10201020base3_10211021base3_10221022base3_11001100base3_11011101base3_11021102base3_11101110base3_11111111base3_11121112base3_11201120base3_11211121base3_11221122base3_12001200base3_12011201base3_12021202base3_12101210base3_12111211base3_12121212base3_12201220base3_12211221base3_12221222base3_20002000base3_20012001base3_20022002base3_20102010base3_20112011base3_20122012base3_20202020base3_20212021base3_20222022base3_21002100base3_21012101base3_21022102base3_21102110base3_21112111base3_21122112base3_21202120base3_21212121base3_21222122base3_22002200base3_22012201base3_22022202base3_22102210base3_22112211base3_22122212base3_22202220base3_22212221base3_22222222base2_low_pass_00000000base2_low_pass_00010001base2_low_pass_00020002base2_low_pass_00110011base2_low_pass_00100010base2_low_pass_00120012base2_low_pass_00210021base2_low_pass_00200020base2_low_pass_00220022base2_low_pass_01110111base2_low_pass_01000100base2_low_pass_01010101base2_low_pass_01020102base2_low_pass_01100110base2_low_pass_01120112base2_low_pass_01210121base2_low_pass_01200120base2_low_pass_01220122base2_low_pass_02110211base2_low_pass_02000200base2_low_pass_02010201base2_low_pass_02020202base2_low_pass_02100210base2_low_pass_02120212base2_low_pass_02210221base2_low_pass_02200220base2_low_pass_02220222base2_low_pass_11111111base2_low_pass_10001000base2_low_pass_10011001base2_low_pass_10021002base2_low_pass_10111011base2_low_pass_10101010base2_low_pass_10121012base2_low_pass_10211021base2_low_pass_10201020base2_low_pass_10221022base2_low_pass_11001100base2_low_pass_11011101base2_low_pass_11021102base2_low_pass_11101110base2_low_pass_11121112base2_low_pass_11211121base2_low_pass_11201120base2_low_pass_11221122base2_low_pass_12111211base2_low_pass_12001200base2_low_pass_12011201base2_low_pass_12021202base2_low_pass_12101210base2_low_pass_12121212base2_low_pass_12211221base2_low_pass_12201220base2_low_pass_12221222base2_low_pass_21112111base2_low_pass_20002000base2_low_pass_20012001base2_low_pass_20022002base2_low_pass_20112011base2_low_pass_20102010base2_low_pass_20122012base2_low_pass_20212021base2_low_pass_20202020base2_low_pass_20222022base2_low_pass_21002100base2_low_pass_21012101base2_low_pass_21022102base2_low_pass_21102110base2_low_pass_21122112base2_low_pass_21212121base2_low_pass_21202120base2_low_pass_21222122base2_low_pass_22112211base2_low_pass_22002200base2_low_pass_22012201base2_low_pass_22022202base2_low_pass_22102210base2_low_pass_22122212base2_low_pass_22212221base2_low_pass_22202220base2_low_pass_22222222base2_00000000base2_00010001base2_00100010base2_00110011base2_01000100base2_01010101base2_01100110base2_01110111base2_10001000base2_10011001base2_10101010base2_10111011base2_11001100base2_11011101base2_11101110base2_11111111base3_0000->base3_0001base3_0001->base3_0000base3_0001->base3_0002base3_0002->base3_0001base3_0002->base3_0010base3_0010->base3_0002base3_0010->base3_0011base3_0011->base3_0010base3_0011->base3_0012base3_0012->base3_0011base3_0012->base3_0020base3_0020->base3_0012base3_0020->base3_0021base3_0021->base3_0020base3_0021->base3_0022base3_0022->base3_0021base3_0022->base3_0100base3_0100->base3_0022base3_0100->base3_0101base3_0101->base3_0100base3_0101->base3_0102base3_0102->base3_0101base3_0102->base3_0110base3_0110->base3_0102base3_0110->base3_0111base3_0111->base3_0110base3_0111->base3_0112base3_0112->base3_0111base3_0112->base3_0120base3_0120->base3_0112base3_0120->base3_0121base3_0121->base3_0120base3_0121->base3_0122base3_0122->base3_0121base3_0122->base3_0200base3_0200->base3_0122base3_0200->base3_0201base3_0201->base3_0200base3_0201->base3_0202base3_0202->base3_0201base3_0202->base3_0210base3_0210->base3_0202base3_0210->base3_0211base3_0211->base3_0210base3_0211->base3_0212base3_0212->base3_0211base3_0212->base3_0220base3_0220->base3_0212base3_0220->base3_0221base3_0221->base3_0220base3_0221->base3_0222base3_0222->base3_0221base3_0222->base3_1000base3_1000->base3_0222base3_1000->base3_1001base3_1001->base3_1000base3_1001->base3_1002base3_1002->base3_1001base3_1002->base3_1010base3_1010->base3_1002base3_1010->base3_1011base3_1011->base3_1010base3_1011->base3_1012base3_1012->base3_1011base3_1012->base3_1020base3_1020->base3_1012base3_1020->base3_1021base3_1021->base3_1020base3_1021->base3_1022base3_1022->base3_1021base3_1022->base3_1100base3_1100->base3_1022base3_1100->base3_1101base3_1101->base3_1100base3_1101->base3_1102base3_1102->base3_1101base3_1102->base3_1110base3_1110->base3_1102base3_1110->base3_1111base3_1111->base3_1110base3_1111->base3_1112base3_1112->base3_1111base3_1112->base3_1120base3_1120->base3_1112base3_1120->base3_1121base3_1121->base3_1120base3_1121->base3_1122base3_1122->base3_1121base3_1122->base3_1200base3_1200->base3_1122base3_1200->base3_1201base3_1201->base3_1200base3_1201->base3_1202base3_1202->base3_1201base3_1202->base3_1210base3_1210->base3_1202base3_1210->base3_1211base3_1211->base3_1210base3_1211->base3_1212base3_1212->base3_1211base3_1212->base3_1220base3_1220->base3_1212base3_1220->base3_1221base3_1221->base3_1220base3_1221->base3_1222base3_1222->base3_1221base3_1222->base3_2000base3_2000->base3_1222base3_2000->base3_2001base3_2001->base3_2000base3_2001->base3_2002base3_2002->base3_2001base3_2002->base3_2010base3_2010->base3_2002base3_2010->base3_2011base3_2011->base3_2010base3_2011->base3_2012base3_2012->base3_2011base3_2012->base3_2020base3_2020->base3_2012base3_2020->base3_2021base3_2021->base3_2020base3_2021->base3_2022base3_2022->base3_2021base3_2022->base3_2100base3_2100->base3_2022base3_2100->base3_2101base3_2101->base3_2100base3_2101->base3_2102base3_2102->base3_2101base3_2102->base3_2110base3_2110->base3_2102base3_2110->base3_2111base3_2111->base3_2110base3_2111->base3_2112base3_2112->base3_2111base3_2112->base3_2120base3_2120->base3_2112base3_2120->base3_2121base3_2121->base3_2120base3_2121->base3_2122base3_2122->base3_2121base3_2122->base3_2200base3_2200->base3_2122base3_2200->base3_2201base3_2201->base3_2200base3_2201->base3_2202base3_2202->base3_2201base3_2202->base3_2210base3_2210->base3_2202base3_2210->base3_2211base3_2211->base3_2210base3_2211->base3_2212base3_2212->base3_2211base3_2212->base3_2220base3_2220->base3_2212base3_2220->base3_2221base3_2221->base3_2220base3_2221->base3_2222base3_2222->base3_2221base2_low_pass_0000->base2_low_pass_0001base2_low_pass_0001->base2_low_pass_0000base2_low_pass_0001->base2_low_pass_0002base2_low_pass_0002->base2_low_pass_0001base2_low_pass_0002->base2_low_pass_0011base2_low_pass_0011->base2_low_pass_0010base2_low_pass_0011->base2_low_pass_0012base2_low_pass_0010->base2_low_pass_0001base2_low_pass_0010->base2_low_pass_0011base2_low_pass_0012->base2_low_pass_0011base2_low_pass_0012->base2_low_pass_0021base2_low_pass_0021->base2_low_pass_0020base2_low_pass_0021->base2_low_pass_0022base2_low_pass_0020->base2_low_pass_0011base2_low_pass_0020->base2_low_pass_0021base2_low_pass_0022->base2_low_pass_0021base2_low_pass_0022->base2_low_pass_0111base2_low_pass_0111->base2_low_pass_0110base2_low_pass_0111->base2_low_pass_0112base2_low_pass_0100->base2_low_pass_0011base2_low_pass_0100->base2_low_pass_0101base2_low_pass_0101->base2_low_pass_0100base2_low_pass_0101->base2_low_pass_0102base2_low_pass_0102->base2_low_pass_0111base2_low_pass_0102->base2_low_pass_0101base2_low_pass_0110->base2_low_pass_0111base2_low_pass_0110->base2_low_pass_0101base2_low_pass_0112->base2_low_pass_0111base2_low_pass_0112->base2_low_pass_0121base2_low_pass_0121->base2_low_pass_0120base2_low_pass_0121->base2_low_pass_0122base2_low_pass_0120->base2_low_pass_0111base2_low_pass_0120->base2_low_pass_0121base2_low_pass_0122->base2_low_pass_0121base2_low_pass_0122->base2_low_pass_0211base2_low_pass_0211->base2_low_pass_0210base2_low_pass_0211->base2_low_pass_0212base2_low_pass_0200->base2_low_pass_0111base2_low_pass_0200->base2_low_pass_0201base2_low_pass_0201->base2_low_pass_0200base2_low_pass_0201->base2_low_pass_0202base2_low_pass_0202->base2_low_pass_0211base2_low_pass_0202->base2_low_pass_0201base2_low_pass_0210->base2_low_pass_0211base2_low_pass_0210->base2_low_pass_0201base2_low_pass_0212->base2_low_pass_0211base2_low_pass_0212->base2_low_pass_0221base2_low_pass_0221->base2_low_pass_0220base2_low_pass_0221->base2_low_pass_0222base2_low_pass_0220->base2_low_pass_0211base2_low_pass_0220->base2_low_pass_0221base2_low_pass_0222->base2_low_pass_0221base2_low_pass_0222->base2_low_pass_1111base2_low_pass_1111->base2_low_pass_1110base2_low_pass_1111->base2_low_pass_1112base2_low_pass_1000->base2_low_pass_0111base2_low_pass_1000->base2_low_pass_1001base2_low_pass_1001->base2_low_pass_1000base2_low_pass_1001->base2_low_pass_1002base2_low_pass_1002->base2_low_pass_1001base2_low_pass_1002->base2_low_pass_1011base2_low_pass_1011->base2_low_pass_1010base2_low_pass_1011->base2_low_pass_1012base2_low_pass_1010->base2_low_pass_1001base2_low_pass_1010->base2_low_pass_1011base2_low_pass_1012->base2_low_pass_1011base2_low_pass_1012->base2_low_pass_1021base2_low_pass_1021->base2_low_pass_1020base2_low_pass_1021->base2_low_pass_1022base2_low_pass_1020->base2_low_pass_1011base2_low_pass_1020->base2_low_pass_1021base2_low_pass_1022->base2_low_pass_1111base2_low_pass_1022->base2_low_pass_1021base2_low_pass_1100->base2_low_pass_1011base2_low_pass_1100->base2_low_pass_1101base2_low_pass_1101->base2_low_pass_1100base2_low_pass_1101->base2_low_pass_1102base2_low_pass_1102->base2_low_pass_1111base2_low_pass_1102->base2_low_pass_1101base2_low_pass_1110->base2_low_pass_1111base2_low_pass_1110->base2_low_pass_1101base2_low_pass_1112->base2_low_pass_1111base2_low_pass_1112->base2_low_pass_1121base2_low_pass_1121->base2_low_pass_1120base2_low_pass_1121->base2_low_pass_1122base2_low_pass_1120->base2_low_pass_1111base2_low_pass_1120->base2_low_pass_1121base2_low_pass_1122->base2_low_pass_1121base2_low_pass_1122->base2_low_pass_1211base2_low_pass_1211->base2_low_pass_1210base2_low_pass_1211->base2_low_pass_1212base2_low_pass_1200->base2_low_pass_1111base2_low_pass_1200->base2_low_pass_1201base2_low_pass_1201->base2_low_pass_1200base2_low_pass_1201->base2_low_pass_1202base2_low_pass_1202->base2_low_pass_1211base2_low_pass_1202->base2_low_pass_1201base2_low_pass_1210->base2_low_pass_1211base2_low_pass_1210->base2_low_pass_1201base2_low_pass_1212->base2_low_pass_1211base2_low_pass_1212->base2_low_pass_1221base2_low_pass_1221->base2_low_pass_1220base2_low_pass_1221->base2_low_pass_1222base2_low_pass_1220->base2_low_pass_1211base2_low_pass_1220->base2_low_pass_1221base2_low_pass_1222->base2_low_pass_1221base2_low_pass_1222->base2_low_pass_2111base2_low_pass_2111->base2_low_pass_2110base2_low_pass_2111->base2_low_pass_2112base2_low_pass_2000->base2_low_pass_1111base2_low_pass_2000->base2_low_pass_2001base2_low_pass_2001->base2_low_pass_2000base2_low_pass_2001->base2_low_pass_2002base2_low_pass_2002->base2_low_pass_2001base2_low_pass_2002->base2_low_pass_2011base2_low_pass_2011->base2_low_pass_2010base2_low_pass_2011->base2_low_pass_2012base2_low_pass_2010->base2_low_pass_2001base2_low_pass_2010->base2_low_pass_2011base2_low_pass_2012->base2_low_pass_2011base2_low_pass_2012->base2_low_pass_2021base2_low_pass_2021->base2_low_pass_2020base2_low_pass_2021->base2_low_pass_2022base2_low_pass_2020->base2_low_pass_2011base2_low_pass_2020->base2_low_pass_2021base2_low_pass_2022->base2_low_pass_2111base2_low_pass_2022->base2_low_pass_2021base2_low_pass_2100->base2_low_pass_2011base2_low_pass_2100->base2_low_pass_2101base2_low_pass_2101->base2_low_pass_2100base2_low_pass_2101->base2_low_pass_2102base2_low_pass_2102->base2_low_pass_2111base2_low_pass_2102->base2_low_pass_2101base2_low_pass_2110->base2_low_pass_2111base2_low_pass_2110->base2_low_pass_2101base2_low_pass_2112->base2_low_pass_2111base2_low_pass_2112->base2_low_pass_2121base2_low_pass_2121->base2_low_pass_2120base2_low_pass_2121->base2_low_pass_2122base2_low_pass_2120->base2_low_pass_2111base2_low_pass_2120->base2_low_pass_2121base2_low_pass_2122->base2_low_pass_2121base2_low_pass_2122->base2_low_pass_2211base2_low_pass_2211->base2_low_pass_2210base2_low_pass_2211->base2_low_pass_2212base2_low_pass_2200->base2_low_pass_2111base2_low_pass_2200->base2_low_pass_2201base2_low_pass_2201->base2_low_pass_2200base2_low_pass_2201->base2_low_pass_2202base2_low_pass_2202->base2_low_pass_2211base2_low_pass_2202->base2_low_pass_2201base2_low_pass_2210->base2_low_pass_2211base2_low_pass_2210->base2_low_pass_2201base2_low_pass_2212->base2_low_pass_2211base2_low_pass_2212->base2_low_pass_2221base2_low_pass_2221->base2_low_pass_2220base2_low_pass_2221->base2_low_pass_2222base2_low_pass_2220->base2_low_pass_2211base2_low_pass_2220->base2_low_pass_2221base2_low_pass_2222->base2_low_pass_2221base2_0000->base2_0001base2_0001->base2_0000base2_0001->base2_0010base2_0010->base2_0001base2_0010->base2_0011base2_0011->base2_0010base2_0011->base2_0100base2_0100->base2_0011base2_0100->base2_0101base2_0101->base2_0100base2_0101->base2_0110base2_0110->base2_0101base2_0110->base2_0111base2_0111->base2_0110base2_0111->base2_1000base2_1000->base2_0111base2_1000->base2_1001base2_1001->base2_1000base2_1001->base2_1010base2_1010->base2_1001base2_1010->base2_1011base2_1011->base2_1010base2_1011->base2_1100base2_1100->base2_1011base2_1100->base2_1101base2_1101->base2_1100base2_1101->base2_1110base2_1110->base2_1101base2_1110->base2_1111base2_1111->base2_1110
... and note that in the implementation it's double ended (the most significant bit is in the middle and shared by the front part and the back part). The accumulation direction is from the middle digit to both ends (the accumulator should be able to accumulate up to 3 (instead of 2) values at a time, e.g. for each digit node on the right, calculate sum of values from its prev digit node, from its left tree root and from its right tree root), then accumulate the ends together yielding the overall accumulated result of the whole container. That's why updating a element at (near) either end and refreshing the accumulated results only takes O(1).
Examples
The untagged pointers are drawn as solid lines. The 0b1-tagged pointers are drawn as dashed lines.
In each sub-sequence, the digit nodes are organized into a circular doubly linked list. Pointers from/to the end node are 0b1-tagged. The end node's next, middle, prev and accumulated_storage are drawn separately to not break graphviz's layout.
In each digit node's each tree, the tree nodes are organized into a perfect binary tree. The pointer from the root tree node to digit node and pointers from leaf tree nodes to list nodes are 0b1-tagged.
In each sub-sequence, the list nodes are organized into a circular doubly linked list. Pointers from/to the end node are 0b1-tagged. The end node is not drawn to not break graphviz's layout.
empty
The projection and accumulation steps are skipped. What's left can be seen as a std::vector/std::deque that never invalidates iterators/references/pointers, or a std::list with random access ability.
augmented_containers::augmented_deque_t<
	char,
	std::allocator<char>
> augmented_deque;
accumulator_only_yield_one_value_string
The projection step is skipped. element_t(char)s are accumulated into accumulated_storage_t(std::string)s.
augmented_containers::augmented_deque_t<
	char,
	std::allocator<char>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_sequence_t<char, std::string>>
	>
>
projector_and_accumulator_yield_one_value_int
sequence 0: the projection step is skipped; accumulator is int operator+(int, int). sequence 1: every 3 element_t(int)s are projected into their std::ranges::max_element, then accumulated into their std::ranges::min.
augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_plus_t<int>>,
		std::pair<std::integral_constant<std::size_t, 3>, augmented_containers::augmented_deque_helpers::example_chunkgt1_projector_max_element_and_accumulator_min_t<int>>
	>
> augmented_deque;
projector_and_accumulator_yield_one_value_string
sequence 0: the projection step is skipped; accumulator is std::string operator+(std::string const&, std::string const&). sequence 1: every 3 element_t(std::string)s are projected into their std::ranges::max_element, then accumulated into their std::ranges::min.
augmented_containers::augmented_deque_t<
	std::string,
	std::allocator<std::string>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_plus_t<std::string>>,
		std::pair<std::integral_constant<std::size_t, 3>, augmented_containers::augmented_deque_helpers::example_chunkgt1_projector_max_element_and_accumulator_min_t<std::string>>
	>
> augmented_deque;
projector_and_accumulator_yield_multiple_values
sequence 0: the projection and accumulation steps are skipped. sequence 1: every 3 element_t(int)s are projected into their std::ranges::stable_sort (stores addresses so you can modify the original elements), then accumulated into their std::ranges::merge | std::views::take(3) (stores addresses so you can modify the original elements).
augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		//std::pair<std::integral_constant<std::size_t, 3>, projector_and_accumulator_min_n_element_t<int, 3>>, //commented one of the sub-sequences because it looks messy when there are three images stacked together
		std::pair<std::integral_constant<std::size_t, 3>, projector_and_accumulator_min_n_element_t<int, 3, true>>
	>
> augmented_deque;
projector_and_accumulator_yield_one_view
each element_t(int)s is projected into the navigator portion (prev and next pointers) to be ready to form a circular doubly linked list. The accumulator takes chunk-begins (std::ranges::prev(it).is_end() || (*std::ranges::prev(it) < 50) != (*it < 50)), discards non-chunk-begins (and takes other accumulated circular doubly linked lists), accumulates them into a circular doubly linked lists representing std::ranges::chunk_by_view of the original sequence.
augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, projector_and_accumulator_diffing_adjacent_element_t>
	>
> augmented_deque;
projector_and_accumulator_yield_multiple_views
Similar to the projector_and_accumulator_yield_one_view example, except that each accumulated_storage_t is "a map from element % 3 to circular doubly linked list's end node" (instead of just "one end node"). The result represents C++32's std::ranges::group_by_view of the original sequence (navigator_style = std::ranges::group_by_view::navigator_style_t::circular_doubly_linked_list, map_container_tt = std::map).
augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, projector_and_accumulator_group_by_t>
	>
> augmented_deque;
Relationship with <algorithm> and <ranges>
The table shows the constructs that augmented_deque_t provides a stronger replacement of and the constructs that are not relevant and the reasons.
headers: <algorithm> <ranges>
use projection to handle (without accumulation) transform adjacent_difference ranges::transform_view ranges::elements_view ranges::keys_view ranges::values_view ranges::adjacent_view ranges::adjacent_transform_view ranges::slide_view ranges::chunk_view ranges::stride_view
use accumulation (possibly after projection) to handle all_of, any_of, none_of count count_if find find_first_of adjacent_find is_partitioned partition_point is_sorted is_sorted_until max_element min_element minmax_element accumulate (reduce, transform_reduce) ranges::join_view ranges::join_with_view
use accumulation (possibly after projection) + read_range to handle partial_sum exclusive_scan (transform_exclusive_scan) inclusive_scan (transform_inclusive_scan)
use yield_multiple_values example to handle nth_element (when n is small) make_heap push_heap pop_heap sort_heap
use yield_one_view example to handle lower_bound (yields one view of iterators, distance > 1 when original sequence is not sorted) upper_bound (yields one view of iterators, distance > 1 when original sequence not sorted) equal_ranges (yields one view of ranges, distance > 1 when original sequence not sorted) ranges::filter_view ranges::take_view ranges::take_while_view ranges::drop_view ranges::drop_while_view ranges::split_view ranges::chunk_by_view
not relevant for_each generate iota ranges::empty_view ranges::single_view ranges::iota_view ranges::basic_istream_view ranges::repeat_view ranges::cartesian_product_view views::all_t ranges::ref_view ranges::owning_view ranges::lazy_split_view views::counted ranges::common_view ranges::reverse_view ranges::as_const_view ranges::as_rvalue_view
aims at order-of/modifying/reordering elements (checks physical storage style/changes physical storage style/changes sequential relationships between elements, for future use) instead of calculating a result, so not relevant copy move fill remove replace swap reverse rotate shift_left shift_right unique partition stable_partition sort partial_sort stable_sort merge inplace_merge is_heap is_heap_until is_permutation next_permutation prev_permutation
calculated result can not be reused and must be recalculated every time, so not relevant shuffle sample
requires domain-specific algorithm, generality is sacrificed, so not relevant search
requires multiple sequences, so not relevant mismatch find_end starts_with ends_with includes set_difference set_intersection set_symmetric_difference set_union equal lexicographical_compare lexicographical_compare_three_way inner_product ranges::zip_view ranges::zip_transform_view